Chapter 4

Conditionals and recursion

based on How to Think Like a Computer Scientist: Python Version :Chapter 4

4.1 The modulus operator

The modulus operator works on integers (and integer expressions) and yields the remainder when the first operand is divided by the second. In Python, the modulus operator is a percent sign, %. 
>>> quotient = 7/3
>>> remainder = 7 % 3
>>> quotient
2
>>> remainder
1
Other uses:

4.2 Conditional execution

Conditional statements allow us to check certain conditions and change the behavior of the program accordingly.

The simplest form is the if statement: 

  if x > 0:
    print "x is positive"
The expression between the if and the : is called the condition. The condition can contain any of the comparison operators: 
    x == y               # x equals y
    x != y               # x is not equal to y
    x > y                # x is greater than y
    x < y                # x is less than y
    x >= y               # x is greater than or equal to y
    x <= y               # x is less than or equal to y
Note that = is the assignment operator, and == is a comparison operator.

4.3 Compound statements

if statements, like function definitions, are compound statements. Their syntax is: 
HEADER:
  FIRST STATEMENT
  ...
  LAST STATEMENT
All the statements in the block are treated as a unit.

4.4 Alternative execution

A second form of the if statement is alternative execution, in which there are two possibilities, and the condition determines which one gets executed: 
  if x%2 == 0:
    print x, "is even"
  else:
    print x, "is odd"
This code could be wrapped in a function: 
  def printParity(x):
    if x%2 == 0:
      print x, "is even"
    else:
      print x, "is odd"

4.5 Multiple branches

Another name for conditional execution is conditional branching, because this type of control structure causes the flow of execution to branch off in different directions.

if is extended to multiple branches with the elif (an abbreviation for "else if"). Here is a trichotomy: 

  if x < y:
    print x, "is less than", y
  elif x > y:
    print x, "is greater than", y
  else:
    print x, "and", y, "are equal"
multiple elif can also be repeated: 
  if choice == 'A':
    functionA()
  elif choice == 'B':
    functionB()
  elif choice == 'C':
    functionC()
  elif choice == 'D':
    functionD()
  else:
     print "Invalid choice."

4.6 Nested conditionals

One conditional can also be nested inside another: 
  if x == y:
    print x, "and", y, "are equal"
  else:
    if x < y:
      print x, "is less than", y
    else:
      print x, "is greater than", y

4.7 The return statement

The return statement allows you to terminate the execution of a function before you reach the end.

One reason to use it is if you detect an error condition: 

  import math

  def printLogarithm(x):
    if x <= 0: 
      print "Positive numbers only, please."
      return

    result = math.log(x)
    print "The log of x is", result
In chapter 5 we will use return to return values from a function.

4.8 Recursion

Functions, besides calling other functions, can also call themselves. This is one of the most magical and interesting things a program can do. 
  def countdown(n):
    if n == 0:
      print "Blastoff!"
    else:
      print n
      countdown(n-1)
let's call it with 
  countdown(3)

The execution of countdown begins with n=3, and since n is not zero, it outputs the value 3, and then calls itself...

The execution of countdown begins with n=2, and since n is not zero, it outputs the value 2, and then calls itself...
The execution of countdown begins with n=1, and since n is not zero, it outputs the value 1, and then calls itself...
The execution of countdown begins with n=0, and since n is zero, it outputs the word ``Blastoff!'' and then returns.
The countdown that got n=1 returns.
The countdown that got n=2 returns.

The countdown that got n=3 returns.

And then you're back in main (what a trip). So the total output looks like:

3
2
1
Blastoff!
As a second example, let's look again at the functions newLine and threeLine.

  def newline():
    print

  def threeLines():
    newLine()
    newLine()
    newLine()

Although these work, they would not be much help if we wanted to output 2 newlines, or 106. A better alternative would be

  def nLines(n):
    if n > 0:
      print
      nLines(n-1)

This program is similar to countdown; as long as n is greater than zero, it outputs one newline, and then calls itself to output n-1 additional newlines. Thus, the total number of newlines is 1 + (n-1), which if you do your algebra right comes out to n.

The process of a function calling itself is called recursion, and such functions are said to be recursive

4.9 Infinite recursion

In previous examples of recursive calls, the argument gets smaller by one in each call, and eventually gets to zero. When the argument is zero the function returns immediately.

The case where the function completes without making any recursive calls is called the base case

If recursion never reaches a base case it will continue making recursive calls forever. This is called infinite recursion.

In Python a finite amount of stack is consumed on each recursive call, and eventually the program will terminate with an error message: 

  RuntimeError: Maximum recursion depth exceeded
For this reason, in Python functions such as nLines are better written using iteration (Chapter 6). If you really want to use recursion instead, try the programming language Scheme.

4.10 Stack diagrams for recursive functions

Here is a stack diagram for countdown(3):

image from How to Think Like a Computer Scientist: Python Version

4.11 Keyboard input

Python provides built-in functions to get input from the keyboard.